<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <title>0-1背包问题和部分背包问题</title>
</head>

<body>
  <h1>0-1背包问题</h1>
  <p>注意：0-1背包不能用贪心算法求解。</p>
  <p>原因：按照贪心算法，每一次拿的都是每磅最贵的物品。由于物品大小不同，有可能每磅最贵的不是最合适大小的。最坏的情况可能导致，背包没有装满，而且当前装的也不是最优的。</p>

  <h1>部分背包问题</h1>
  <p>问题：假设物体重量5，20，10，12，其对应的价值为50，140，60，60，物体可分割，求装入重量限制为30的背包中的物体价值最大</p>
  <p>解决思路：部分背包，显而易见可以用贪心算法。每件物品，以价值排序，每次优先选取价值大的，若物品选光则选次大的，直到背包装不下。</p>
  <p>结果：</p>
  <script src="./part-knapsack.js" charset="utf-8"></script>
</body>

</html>
